package com.zhaofan.sort;

import org.junit.Test;

import javax.xml.bind.annotation.adapters.HexBinaryAdapter;
import javax.xml.soap.Node;
import java.awt.*;

public class No148 {

    @Test
    public void test1() {
        int[] a = {4, 2, 1, 3};
        ListNode node = new ListNode();
//        node.val=Integer.MIN_VALUE;
        ListNode head = node;
        for (int i = 0; i < a.length; i++) {
            ListNode temp = new ListNode();
            temp.val = a[i];
            node.next = temp;
            node = temp;
        }

        head = sortList(head);

        while (head != null) {
            System.out.println(head.val);
            head = head.next;

        }
    }


    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode lastInputNode;
        ListNode result = new ListNode();
        result.val = Integer.MIN_VALUE;
        ListNode resultFor = result;
        ListNode lastNode = null;
        while (head != null) {
            while (true) {
                if (head.val >= resultFor.val) {
                    lastNode = resultFor;
                } else if (head.val < resultFor.val) {//如果小于当前循环值的话,就要将当前节点插入到lastNode节点之后,并将tempNode节点的next指向当前节点
                    ListNode tempNode = new ListNode(head.val, resultFor);
                    lastNode.next = tempNode;
                    lastNode = resultFor;
                    break;
                } else if (resultFor.next == null) {
                    ListNode temp = new ListNode();
                    temp.val = head.val;
                    resultFor.next = temp;
                    break;
                }
                resultFor = resultFor.next;
            }
            resultFor = result;
            lastNode = null;
            head = head.next;
        }
        return result;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;


        }
    }
}
